
class Solution:

    def coinChange(self, coins, amount: int) -> int:
        dp = [None] * (amount + 1)
        dp[0] = 0
        coins.sort()
        for i in range(1, amount + 1):
            minVal = None
            for j in coins:
                k = i - j
                if k < 0:
                    break
                if dp[k] is None:
                    continue
                nowVal = dp[k] + 1
                if minVal is None:
                    minVal = nowVal
                else:
                    minVal = min(minVal, nowVal)
            dp[i] = minVal
        return dp[-1] if dp[-1] is not None else -1

if __name__ == '__main__':
    so = Solution()
    coins = [2]
    amount = 3
    r = so.coinChange(coins, amount)
    print(r)
